#include <stdio.h>
#include <stdlib.h>

static int queen_num;
static int *x;
static int solution_num;

void print_solution()
{
	solution_num++;
#if 0
	for (int i = 1; i <= queen_num; i++)
		printf("%-3d ", x[i]);
	printf("\n");
#endif
}

int try_place(int k)
{
	for (int j = 1; j < k; j++) {
		if (abs(x[k] - x[j]) == abs(k - j) || x[k] == x[j])
			return 0;
	}
	return 1;
}

void back_track(int k)
{
	if (k > queen_num)
		print_solution();
	else
		for (int i = 1; i <= queen_num; i++) {
			x[k] = i;
			if (try_place(k))
				back_track(k + 1);
		}
}

#define MAX_QUEENS 26
int main(int argc, char *argv[])
{
	x = (int *)malloc((MAX_QUEENS + 1) * sizeof(int));

	for (int i = 4; i <= MAX_QUEENS; i++) {
		queen_num = i;
		solution_num = 0;
		back_track(1);
		printf("%-2d queens # of solutions: %d\n", i, solution_num);
	}
	
	return 0;
}
